home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15386 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: howland.reston.ans.net!psinntp!psinntp!psinntp!pipeline!not-for-mail
  2. From: digiulio@nyc.pipeline.com (Thomas DiGiulio)
  3. Newsgroups: comp.lang.c++,
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 4 Apr 1996 23:12:43 -0500
  6. Organization: The Pipeline
  7. Message-ID: <4k26jr$1cj@pipe10.nyc.pipeline.com>
  8. References: <DpAxtI.3w9@undergrad.math.uwaterloo.ca>
  9. NNTP-Posting-Host: pipe10.nyc.pipeline.com
  10. X-PipeUser: digiulio
  11. X-PipeHub: nyc.pipeline.com
  12. X-PipeGCOS: (Tom DiGiulio)
  13. X-Newsreader: Pipeline v3.5.0
  14.  
  15. On Apr 03, 1996 19:51:18 in article <Re: Fastest Sorting Algorithm?>,
  16. 'sckettle@undergrad.math.uwaterloo.ca (Steve Kettle)' wrote: 
  17.  
  18.  
  19. >In article <Dou55w.7MB@novice.uwaterloo.ca>, 
  20. >Gerald Wang  <GTWANG@HELIX.Watstar.UWaterloo.CA> wrote: 
  21. >>A classmate was recently asked during a job interview what is the fastest
  22.  
  23. >>method to sort an array of numbers. He replied "Use a quicksort." They  
  24. >>asked "And how would you make it faster still?" He couldn't come up with 
  25.  
  26. >>much...end of interview. 
  27. >> 
  28. >>I know it's a vague question... Any ideas on what they were asking? Or  
  29. >>what the right answer is? 
  30. >> 
  31. >>Gerald 
  32. >> 
  33. >>-------------------------------------------------------------------------
  34.  
  35. >>Gerald Wang 
  36. >>http://www.csclub.uwaterloo.ca/~gtwang 
  37. >> 
  38. >> 
  39. > 
  40. >Well you could use a type of bucket sorting algorithm which is faster than
  41.  
  42. >quicksort when sorting integers.  How to make it faster I don't know - you
  43.  
  44. >don't really make algortithms faster you make code implementations of 
  45. >algorithms faster. Mybe they meant tweaking stratigies for quicksort like
  46. how 
  47. >to choose a pivot element.  Who knows.  
  48. > 
  49.  
  50. I came upon this question, and decided to do a liitle research.  Sitting on
  51. my bookshelf was a good book (IMHO) that I had used 
  52. in an "Analysis of Algorithms" course - "Data Structures and Algorithms" by
  53. Aho, Hopcroft, and Ullman. 
  54.  
  55. In a section entitled "Improvements to Quicksort" (p.270) they mention that
  56. the quicksort is indeed fast, and "its running time is less than that of
  57. all other currently known O(n log n) sorting algorithms..." 
  58.  
  59. In the average case it is on the O(n log n), and degrades to O(n^2) in the
  60. worst case. 
  61.  
  62. Briefly, among the improvements that can be made: 
  63.  
  64. 1) devise a way to pick pivot elements that divide the subarrays so that
  65. each subarray has relatively the same # of elements. 
  66.  
  67. 2) If you are willing to sacrifice space for time, create an array of
  68. pointers, which point to the records in the array.  Move the pointers in
  69. the same manner as the quicksort  would move the records, and the pointers
  70. would point to the records in sorted order.This would reduce the number of
  71. swaps from O(n log n) to n. 
  72.  
  73. I hope this paraphrase made sense.  Hope this helped. 
  74.  
  75. Tom 
  76. -- 
  77. digiulio@pipeline.com  
  78.